`
https://leetcode.cn/problems/time-based-key-value-store/
`

// 题同 LC 1146

var TimeMap = function () {
  // key -> [[timestamp, value], [...], ...]
  // 题目保证 set 调用时严格递增 timestamp
  // 所以数组里的 timestamp 都是严格递增的
  this.ts = new Map()
};

/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  // 拿到对应的记录数组
  if (!this.ts.has(key)) {
    this.ts.set(key, [])
  }
  const target = this.ts.get(key)
  // 没有记录或最后位置不是当前 timestamp ，传个新的进去
  if (target.length === 0 || target.at(-1)[0] !== timestamp) {
    target.push([timestamp, value])
    return
  }
  // 否则直接更新值即可
  target.at(-1)[1] = value
};

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
  // 拿到对应的记录数组
  const target = this.ts.get(key) || []
  // 没有记录直接返回空串
  if (target.length === 0) return ""
  // 找到最后一个 <= timestamp 的位置
  const recordIdx = _.sortedIndexBy(target, [timestamp + 1], ([timestamp]) => timestamp) - 1
  // 如果在 timestamp 之前没记录，返回空串
  if (recordIdx === -1) return ""
  return target[recordIdx][1]
};

/** 
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */